class Solution {
	public:
		bool VerifySquenceOfBST(vector<int> sequence) {
			if(sequence.empty())
				return false;
			return _VerifySquenceOfBST(sequence, 0, sequence.size()-1);
		}
		bool _VerifySquenceOfBST(const vector<int>& v, int first, int last){
			//只有一个结点的情况
			if(first >= last)
				return true;
			int rootValue = v[last];    //从最右边确定根结点
			int l = first;
			//从左向右遍历寻找值大于rootValue的结点
			while(l < last){
				if(v[l] > rootValue){
					break;
				}
				l++;
			}
			//左单支,且满足后序结果
			//为什么不判断右单支的情况?
			if(l == last){
				return true;
			}

			//此时判断右边有没有比rootValue小的数，有的话返回false
			int index = l;
			while(index++ < last){
				if(v[index] < rootValue){
					return false;
				}
			}
			return _VerifySquenceOfBST(v, 0, l - 1) && _VerifySquenceOfBST(v, l, last - 1);
		}
};
